package Test;

import java.util.Stack;

class Graph {
    int[][] matrix;       // 图的邻接矩阵
    int n;                // 顶点个数
    boolean[] visited;    //标记点是否被访问
    int[] ans = new int[50];
    int count = 0;        //记录欧拉路的路径，路径数
    Stack<Integer> stack = new Stack();

    public Graph(int[][] matrix, int n) {
        this.matrix = matrix;
        this.n = n;
        visited = new boolean[n];
        for(int i = 0; i < n; i++){
            visited[i] = false;
        }
    }

    //从所设定的起点深度优先遍历图，若存在顶点未被访问，则为非连通图
    public boolean Judge() {
        DFS(0);
        for(int i = 0; i < n; i++)
            if(!visited[i])
                return false;
        return true;
    }

    //深度优先搜索
    private void DFS(int x) {
        visited[x] = true;
        for(int i = 0; i < n; i++)
            if(!visited[i] && matrix[x][i]==1)
                DFS(i);
    }

    public void JudgeEuler() {
        int degree, start = 0, num = 0;

        // 如果存在奇度顶点，则从奇度顶点出发，否则从0出发
        for(int i = 0; i < n; i++) {
            degree = 0;
            for(int j = 0; j < n; j++)
                degree += matrix[i][j];
            if(degree % 2!=0) {
                start = i;
                num++;
            }
        }

        // 无向图具有一条欧拉路，当且仅当G是连通的，且有0个或2个奇数度结点
        if(num == 0 || num == 2) {
            Fleury(start);
            //欧拉路径的头和尾相等，则说明欧拉路是回路
            if(ans[0] == ans[count - 1])
                System.out.println("该图是欧拉图，欧拉回路为：");
            else
                System.out.println("该图是半欧拉图，欧拉路为：");
            Answer();
        }
        else
            System.out.println("该图不是欧拉图或半欧拉图");
    }

    private void Answer() {
        for(int i = 0; i < count; i++)
            System.out.print(ans[i]+" ");
        System.out.println();
    }

    private void Fleury(int x) {
        int flag;
        stack.push(x);
        while(!stack.isEmpty()) {
            flag = 0;
            for(int i = 0; i < n; i++) {
                if(matrix[stack.lastElement()][i] > 0) {
                    flag = 1;
                    break;
                }
            }
            //如果没有可扩展的点，则记录下该点并将其出栈
            if(flag == 0)
                ans[count ++] = stack.pop() + 1;
            //如果有，则将其出栈并继续搜索
            else
                DFSGraph(stack.pop());
        }
    }

    private void DFSGraph(int x) {
        stack.push(x);
        for(int i = 0; i < n; i++) {
            if(matrix[i][x] > 0) {
                matrix[i][x] = 0;  //删除该边
                matrix[x][i] = 0;
                DFSGraph(i);
                break;
            }
        }
    }
}


